package class11;

import java.sql.Time;
import java.util.Arrays;

/**
 * 动态规划问题
 * https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/description/
 *
 * 斐波那契数列
 */
public class Code01_DP {
    static int n = 8;

    public static void main(String[] args) {

//        printFip(n);
        // 方法1
//        System.out.println("fip1(n) = " + fip1(n));
        // 方法2
//        System.out.println("fip2(n) = " + fip2(n));

        System.out.println("fip3(n) = " + fip3(n));


    }

    public static void printFip(int n) {
        for (int i = 0; i <= n; i++) {
            System.out.println("第" + i + "项：" + fip1(i) + " ");
        }
        System.out.println();
    }

    /**
     * 斐波那契额数列解法1
     * 0 1 1 2 3 5 8 13
     * 如果第8项是13，那么13是 (n-1) + (n-2)项的值得到的
     */
    public static int fip1(int n) {
        if (n <= 1) {
            return n;
        }
        return fip1(n - 1) + fip1(n - 2);
    }

    /**
     * 利用缓存表，记录已经计算过的斐波那契额数列
     */
    public static int fip2(int n) {
        int[] table = new int[n + 1];
        Arrays.fill(table, -1);

        return f2(n, table);
    }

    public static int f2(int n, int[] table) {
        if (n <= 1) {
            return n;
        }
        if (table[n] != -1) {
            return table[n];
        }
        int ans = f2(n - 1, table) + f2(n - 2, table);
        ans = (int) (ans % (1e9 + 7));
        table[n] = ans;
        return ans;
    }

    /**
     * 利用非递归进行计算,
     * 利用两个变量进行相加获取结果
     */
    public static int fip3(int n) {
        int ans = 0;
        int n0 = 0, n1 = 1;
        for (int i = 1; i < n; i++) {
            ans = (int)((n0 + n1)% (1e9 + 7));
            n0 = n1;
            n1 = ans;
        }
        return ans;
    }

}
